package com.peng.leetcode.tree;

import java.util.*;

/**
 * SubtreeWithAllDeepest
 * <p>
 * 865. 具有所有最深节点的最小子树
 *
 * @author: lupeng6
 * @create: 2021/2/5 14:42
 */
public class SubtreeWithAllDeepest1 {

    public static void main(String[] args) {
        Integer[] arr = {0,1,2,3,7,4,5,6,8,null,9};
        TreeNode treeNode = TreeMain.array2tree(arr);
        TreeNode node = new SubtreeWithAllDeepest1().subtreeWithAllDeepest(treeNode);
        System.out.println(node);
    }

    private Map<TreeNode, TreeNode> parent = new HashMap<>();
    private Map<Integer, List<TreeNode>> depthMap = new HashMap<>();
    private int maxDepth = 0;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }

        // 层级遍历 记录父子关系, 节点深度
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            maxDepth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                depthMap.putIfAbsent(maxDepth, new ArrayList<>());
                depthMap.get(maxDepth).add(node);

                if (node.left != null) {
                    parent.put(node.left, node);
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    parent.put(node.right, node);
                    queue.offer(node.right);
                }
            }
        }

        List<TreeNode> maxDepthNode = depthMap.get(maxDepth);
        if (maxDepthNode.size() == 1) {
            return maxDepthNode.get(0);
        }

        // 最大深度的几点数量大于1, 两个节点一组寻找最近公共祖先
        Deque<TreeNode> stack = new LinkedList<>();
        maxDepthNode.forEach(stack::push);

        while (stack.size() > 1) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();
            TreeNode ancestor = findAncestor(node1, node2);
            stack.push(ancestor);
        }
        return stack.pop();
    }

    TreeNode findAncestor(TreeNode node1, TreeNode node2) {
        Set<TreeNode> node1Ancestor = new HashSet<>();
        node1Ancestor.add(node1);
        while (node1 != null) {
            node1 = parent.get(node1);
            node1Ancestor.add(node1);
        }

        while (node2 != null) {
            node2 = parent.get(node2);
            if (node1Ancestor.contains(node2)) {
                return node2;
            }
        }
        return null;
    }
}
